package dataStructure.graph;

//对边的权重排序，依次选取最小边，选取后结点加入访问集合

/**
 * 最小生成树
 */
public class Kruskal {
    private static final int INF = Integer.MAX_VALUE;

    /**
     * 初始化距离矩阵
     *
     * @param graph 图
     * @return 距离矩阵
     */
    private static int[][] initDistance(GraphMatrix graph) {
        int vertexNum = graph.getVertexNum();
        int[][] result = new int[vertexNum][vertexNum];
        // 初始化距离矩阵
        for (int i = 0; i < vertexNum; i++) {
            for (int j = 0; j < vertexNum; j++) {
                result[i][j] = graph.edges[i][j];
                if (i != j && result[i][j] == 0) {
                    result[i][j] = INF;
                }
            }
        }
        return result;
    }

    private static void kruskal(GraphMatrix graph) {
        //顶点个数
        int num = graph.getVertexNum();
        //存放对应顶点所在连通图标识
        int[] group = new int[num];

        int sum = 0, n1 = 0, n2 = 0;
        boolean finished = false;
        int groupNum = 1;
        int[][] distance = initDistance(graph);
        while (!finished) {
            System.out.print("group:");
            for (int i : group) {
                System.out.print(i + " ");
            }
            System.out.println();
            int min = INF;
            //找出所有边中最小值
            for (int i = 0; i < num; i++) {
                for (int j = i + 1; j < num; j++) {
                    if (distance[i][j] > 0 && distance[i][j] < min) {
                        //如果group相同，则表示处理过，不相同或都为0都表示没处理过
                        if (group[i] != group[j] || (group[i] == 0 && group[j] == 0)) {
                            min = distance[i][j];
                            n1 = i;
                            n2 = j;
                        }
                    }
                }
            }

            if (min == INF) {
                continue;
            }

            System.out.println(graph.vertexList.get(n1) + "->" + graph.vertexList.get(n2) + " " + min);
            sum += min;

            //找到了最小值，设置连通标记
            if (group[n1] == 0 && group[n2] == 0) {
                group[n1] = groupNum;
                group[n2] = groupNum;
                groupNum++;
            } else if (group[n1] > 0 && group[n2] > 0) {
                int tmp = group[n2];
                for (int i = 0; i < group.length; i++) {
                    if (group[i] == tmp) {
                        group[i] = group[n1];
                    }
                }
            } else if (group[n1] == 0) {
                group[n1] = group[n2];
            } else {
                group[n2] = group[n1];
            }

            //检测是否完成
            finished = true;
            for (int aGroup : group) {
                if (aGroup != group[0]) {
                    finished = false;
                    break;
                }
            }
        }
        System.out.println("sum:" + sum);
    }

    public static void main(String[] args) {
        GraphMatrix<String> graph = new GraphMatrix<>("ABCDEF");
        graph.addEdge("A", "B", 6);
        graph.addEdge("A", "C", 1);
        graph.addEdge("A", "D", 5);
        graph.addEdge("B", "C", 5);
        graph.addEdge("B", "E", 3);
        graph.addEdge("C", "D", 5);
        graph.addEdge("C", "E", 6);
        graph.addEdge("C", "F", 4);
        graph.addEdge("D", "F", 2);
        graph.addEdge("E", "F", 6);
        graph.information();
        kruskal(graph);
    }
}
